﻿/*
素数问题 
Time Limit:1000MS  Memory Limit:32768K

  
Description:
任何一个整数，都可以有多个素数相乘，现在给你一个数N(1< N<=65535)，请你把它分成多个素数相乘。

Input:
输入一个整数N，输入0表示结束. 
Output:
输出相应的结果. 
Sample Input:
2
12
16
65535
0
Sample Output:
2
2*2*3
2*2*2*2
3*5*17*257
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
	vector<int> v;
	for (int num; cin>>num && num; v.push_back(num));
	int maximum=*max_element(v.begin(), v.end());

	vector<int> primes;
	primes.push_back(2);
	primes.push_back(3);
	primes.push_back(5);
//	int maximum=100;

	int integer=5;
	int gap=2;
	while (integer<=maximum)//
	{
		integer+=gap;
		gap=6-gap;
		bool is_prime=true;
		for (int i=2; primes[i]*primes[i]<=integer && is_prime; i++)
			if(0==integer%primes[i])
				is_prime=false;
		if(is_prime)
			primes.push_back(integer);
	}
	copy(primes.begin(), primes.end(), ostream_iterator<int>(cout, " "));

	for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
	{
		int num=*it;

		if(1==num || 2==num || 3==num)
		{
			cout<<num<<endl;
			continue;
		}
		for (vector<int>::iterator pit=primes.begin(); pit!=primes.end(); ++pit)
		{
			while (0==(num%(*pit)))
			{
				cout<<(*pit);
				num/=(*pit);
				if(1==num || 0==num)
				{
					cout<<endl;
					break;
				}
				else
					cout<<"*";
			}
		}
	}


	return 0;
}